/**
 * 堆排序
 * 初始化大顶堆时 是从最后一个有子节点开始往上调整最大堆。而堆顶元素(最大数)与堆最后一个数交换后，需再次调整成大顶堆，此时是从上往下调整的。
 * 堆排序很重要的一个步骤是初始建堆，它保证了树中的每个子树的根结点都比其下的子结点大。（对堆中的元素大概排好序了）
 * 父节点：i==0 ? null : (i-1)/2
 *左孩子：2*i + 1
 *右孩子：2*i + 2
 */
public class HeapSort {
//    将元素array[k]自下而上逐步调整树形结构
    private void adjustDownToUp(Integer[] array,int k,int length){
        int temp=array[k];
        for(int i=2*k+1;i<length-1;i=2*i+1){ //i为初始化为节点k的左孩子，沿节点较大的子节点向下调整
            if(i<length&&array[i]<array[i+1]){ //取节点较大的子节点的下标
                i++; //如果节点的右孩子>左孩子，则取右孩子节点的下标
            }
            if(temp>=array[i]){ //根节点 >=左右子女中关键字较大者，调整结束
                break;
            }else{ //根节点 <左右子女中关键字较大者
                array[k]=array[i]; //将左右子结点中较大值array[i]调整到双亲节点上
                k=i; //【关键】修改k值，以便继续向下调整
            }
        }
        array[k]=temp; //被调整的结点的值放入最终位置
    }
//    构建大顶堆：将array看成完全二叉树的顺序存储结构
    private Integer[] buildMaxHeap(Integer[] array){
        //从最后一个节点array.length-1的父节点（array.length-1-1）/2开始，直到根节点0，反复调整堆
        for(int i = (array.length-2)/2;i>=0;i--){
            adjustDownToUp(array,i,array.length);
        }
        return array;
    }
//    堆排序
    public Integer[] heapSort(Integer[] array){
        array=buildMaxHeap(array); //初始建堆，array[0]为第一趟值最大的元素
        for(int i=array.length-1;i>1;i--){
            int temp=array[0];
            array[0]=array[i];
            array[i]=temp;
            adjustDownToUp(array,0,i);//整理，将剩余的元素整理成堆
        }
        return array;
    }
}
